package swordoffer.offer38;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BackTrace {
    public String[] permutation(String s) {
        int len = s.length();
        if (len == 0) {
            return new String[0];
        }
        char[] chs = s.toCharArray();
        Arrays.sort(chs);
        boolean[] visited = new boolean[len];
        List<String> res = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        dfs(chs, 0, path, visited, res);
        return res.toArray(new String[0]);
    }

    public void dfs(char[] chs, int depth, StringBuilder path, boolean[] visited, List<String> res) {
        if (depth == chs.length) {
            res.add(path.toString());
            return;
        }
        for (int i = 0; i < chs.length; i++) {
            if (i > 0 && chs[i] == chs[i - 1] && visited[i - 1] == false) {
                continue;
            }
            if (visited[i] == false) {
                path.append(chs[i]);
                visited[i] = true;
                dfs(chs, depth + 1, path, visited, res);
                visited[i] = false;
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}
